package 美团;

import 树.TreeNode;
import 链表.ListNode;

import java.util.ArrayList;
import java.util.List;


public class _109_有序链表转换二叉搜索树 {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        Integer[] arr = list.toArray(new Integer[]{});
        TreeNode bst = buildBST(arr, 0, arr.length);
        return bst;
    }

    private TreeNode buildBST(Integer[] arr, int begin, int end) {
        if (begin > end) return null;
        int mid = begin + ((end - begin) >> 1);
        TreeNode root = new TreeNode(arr[mid]);
        root.left = buildBST(arr, begin, mid);
        root.right = buildBST(arr, mid + 1, end);
        return root;
    }
}
